package cn.xkai.exercise.b;

/**
 * @description: 计数质数
 * 自己的思路：暴力遍历：超时；存储已发现的质数，然后根据质数组里面的数进行判断，还是超时；
 * 借鉴的思路：
 *  "埃氏筛"：埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
 *          要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
 * @author: kaixiang
 * @date: 2022-07-14
 **/
public class Solution57 {
    public int countPrimes(int n) {
        boolean[] arr = new boolean[n];
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (arr[i]) {
                continue;
            }
            cnt++;
            for (int j = i; j < n; j += i) {
                arr[j] = true;
            }
        }
        return cnt;
    }

    public int countPrimesOutTime(int n) {
        if (n <= 2) {
            return 0;
        }
        int count = 1;
        for (int i = n - 1; i > 2; i--) {
            boolean flag = true;
            int max = new Double(Math.ceil(Math.sqrt(i))).intValue() + 1;
            for (int j = 2; j < max; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int n = 10;
        Solution57 solution57 = new Solution57();
        System.out.println(solution57.countPrimes(n));
    }
}
